\chapter{Duals, adjoint, and transposes}
\label{ch:duals_adjoint_transposes}
This chapter is dedicated to the basis-free interpretation
of the transpose and conjugate transpose of a matrix.

Poster corollary: we will see that
symmetric matrices with real coefficients
are diagonalizable and have real eigenvalues.

\section{Dual of a map}
\prototype{The example below.}
We go ahead and now define a notion
that will grow up to be the transpose of a matrix.

\begin{definition}
	Let $V$ and $W$ be vector spaces.
	Suppose $T \colon V \to W$ is a linear map.
	Then we actually get a map
	\begin{align*}
		T^\vee \colon W^\vee &\to V^\vee \\
		f &\mapsto f \circ T.
	\end{align*}
	This map is called the \vocab{dual map}.
\end{definition}

\begin{example}
	[Example of a dual map]
	Work over $\RR$.
	Let's consider $V$ with basis $e_1$, $e_2$, $e_3$
	and $W$ with basis $f_1$, $f_2$.
	Suppose that
	\begin{align*}
		T(e_1) &= f_1 + 2f_2 \\
		T(e_2) &= 3f_1 + 4f_2 \\
		T(e_3) &= 5f_1 + 6f_2.
	\end{align*}
	Now consider $V^\vee$ with its dual basis $e_1^\vee$,
	$e_2^\vee$, $e_3^\vee$
	and $W^\vee$ with its dual basis $f_1^\vee$, $f_2^\vee$.
	Let's compute $T^\vee(f_1^\vee) = f_1^\vee \circ T$:
	it is given by
	\begin{align*}
		f_1^\vee \left( T(ae_1 + be_2 + ce_3) \right)
		&= f_1^\vee\left( (a+3b+5c) f_1 + (2a+4b+6c) f_2 \right) \\
		&= a + 3b + 5c.
	\end{align*}
	So accordingly we can write
	\[ T^\vee(f_1^\vee) = e_1^\vee + 3e_2^\vee + 5e_3^\vee \]
	Similarly,
	\[ T^\vee(f_2^\vee) = 2e_1^\vee + 4e_2^\vee + 6e_3^\vee. \]
	This determines $T^\vee$ completely.
\end{example}
If we write the matrices for $T$ and $T^\vee$ in terms of our basis,
we now see that
\[ T = \begin{bmatrix}
		1 & 3 & 5 \\
		2 & 4 & 6
	\end{bmatrix}
	\quad\text{and}\quad
	T^\vee = \begin{bmatrix}
		1 & 2 \\
		3 & 4 \\
		5 & 6
	\end{bmatrix}.
\]
So in our selected basis,
we find that the matrices are \vocab{transposes}:
mirror images of each other over the diagonal.

Of course, this should work in general.
\begin{theorem}
	[Transpose interpretation of $T^\vee$]
	\label{thm:transpose_dual}
	Let $V$ and $W$ be finite-dimensional $k$-vector spaces,
	with $e_1$, \dots, $e_n$ any basis for $V$
	with $f_1$, \dots, $f_m$ any basis for $V$.
	Then, for any $T \colon V \to W$, the following two matrices are transposes:
	\begin{itemize}
		\ii The matrix for $T \colon V \to W$
		expressed in the basis $(e_i)$, $(f_j)$.
		\ii The matrix for $T^\vee \colon W^\vee \to V^\vee$
		expressed in the basis $(f_j^\vee)$, $(e_i^\vee)$.
	\end{itemize}
\end{theorem}
\begin{proof}
	The $(i,j)$th entry of the matrix $T$
	corresponds to the coefficient of $f_i$ in $T(e_j)$,
	which corresponds to the coefficient of $e_j^\vee$
	in $f_i^\vee \circ T$.
\end{proof}
The nice part of this is that the definition of $T^\vee$ is basis-free.
So it means that if we start with any linear map $T$,
and then pick whichever basis we feel like,
then $T$ and $T^\vee$ will still be transposes.

\section{(Optional) A cautionary tale on what goes wrong if you don't have a natural isomorphism $V \cong V^\vee$}
After this section, we are going to assume that $V$ and $W$ are in fact inner product spaces.
This optional cautionary section is meant to explain what goes wrong \emph{without} that assumption.
However, this section is really confusing and disorienting,
so you might want to skip it until after you've finished the rest of the chapter
and solved a couple of the problems at the end (like \Cref{prob:row_rank_column_rank}).

For example, by just using \Cref{thm:transpose_dual} you can already prove the following,
which is one of the most important theorems in a typical high-school linear algebra class.
\begin{theorem}
	[Row rank = column rank]
	A $m \times n$ matrix $M$ is given over some field $k$.
	The \emph{column rank} of $M$ is the dimension of the span in $k^{\oplus m}$
	of its $n$ column vectors.
	The \emph{row rank} of $M$ is the dimension of the span in $k^{\oplus n}$
	of its $m$ row vectors.
	Prove that the row rank and column rank are equal.
\end{theorem}
\begin{proof}
	Left as \Cref{prob:fundamental_theorem_of_linalg} and \Cref{prob:row_rank_column_rank}.
	One approach is to combine \Cref{thm:linear_map_basis} and \Cref{thm:transpose_dual}.
\end{proof}

However, let's see what can go wrong if we try to overplay our non-canonical isomorphism
$V \to V^\vee$ with $e_i \mapsto e_i^\vee$.
Let's consider the following ``theorem'':
\begin{tcolorbox}
	\textbf{False Theorem.}
	A $m \times n$ matrix $M$ is given over some field $k$.
	Then $M^\top M$ and $M$ have the same rank.
\end{tcolorbox}

We proceed to give a bogus proof of this result.
\begin{proof}[WRONG Proof of False Theorem]
	Let $V = k^{\oplus n}$, $W = k^{\oplus m}$,
	and let $T \colon V \to W$ be the linear map encoded by $M$.
	By \Cref{thm:transpose_dual}, $T^\vee \colon W^\vee \to V^\vee$
	is encoded as $M^\top$.

	By \Cref{thm:linear_map_basis},
	there exists different bases $e_i$ (for $V$) and $f_j$ (for $W$) such that
	\begin{align*}
		T(e_1) &= f_1, \; \dots, \; T(e_k) = f_k \\
		T(e_{k+1}) &= \dots = T(e_n) = 0
	\end{align*}
	where $k = \rank T$.
	(Sorry for using the letter $k$ for both the rank and the base field.)
	We won't use this new basis for any matrix encodings,
	just to compute the ranks.

	Then, from the definition of $T^\vee \colon W^\vee \to V^\vee$ we can see
	\begin{align*}
		T^\vee(f_1^\vee) &= e_1^\vee, \; \dots, \; T^\vee(f_k^\vee) = e_k^\vee \\
		T^\vee(f_{k+1}^\vee) &= \dots = T(f_m^\vee) = 0.
	\end{align*}
	We can then combine this with our (non-canonical) isomorphism $W \to W^\vee$
	to get that $M^\top M$ is the matrix for the composed map $V \to V^\vee$ by
	\begin{align*}
		e_1 & \mapsto f_1 \mapsto f_1^\vee \mapsto e_1^\vee \\
		e_2 & \mapsto f_2 \mapsto f_2^\vee \mapsto e_2^\vee \\
		&\vdotswithin\mapsto \\
		e_k & \mapsto f_k \mapsto f_k^\vee \mapsto e_k^\vee \\
		e_{k+1} &\mapsto 0 \mapsto 0 \mapsto 0 \\
		e_{k+2} &\mapsto 0 \mapsto 0 \mapsto 0 \\
		&\vdotswithin\mapsto \\
		e_n &\mapsto 0 \mapsto 0 \mapsto 0.
	\end{align*}
	It's clear that this composed map also has rank $k$,
	since the outputs on $e_1$ through $e_k$ are linearly independent
	and the outputs on $e_{k+1}$ through $e_n$ are all $0$.
	Hence, $M^\top M$ also has rank $k$, as desired.
\end{proof}

Seems okay?
But as we'll see in \Cref{prob:rank_Mdagger_M}, the theorem \emph{is}
actually true when $k = \RR$.
But it is false when $k = \CC$, as the following exercise shows:
\begin{exercise}
	Find a counterexample to the fake theorem
	by giving an example of a nonzero $2 \times 2$ matrix $M$ with complex entries
	for which $M^\top M$ is the zero matrix.
\end{exercise}

So where is the mistake in the bogus proof?
I would say the issue is that the map given above by
\[ e_i \mapsto f_i \mapsto f_i^\vee \mapsto e_i^\vee \]
is not $T^\vee \circ T$ (which is not even defined),
but rather $T^\vee \circ \iota \circ T$
where $\iota \colon W \to W^\vee$ is a ``random'' isomorphism that we know nothing about.
Hence, when encoded as a matrix,
the matrix we would get is actually $M^\top N M$
where $N$ is some random invertible matrix we have no control over.

You can fix this proof for $k = \RR$ if you
\begin{itemize}
	\ii Choose $\iota$ to be the map $w \mapsto \left\langle -, w \right\rangle$
	defined in the next section, so that $N$ encodes as the identity matrix; and
	\ii Additionally, require $f_i$ to be orthonormal in \Cref{thm:linear_map_basis}
	(which is possible) so that $\iota(f_i) = f_i^\vee$.
\end{itemize}
However this is a fairly ugly proof in my opinion,
because by the end of the chapter we'll have the tools to write
a basis-free proof for \Cref{prob:rank_Mdagger_M}.

\section{Identifying with the dual space}
For the rest of this chapter, though,
we'll now bring inner products into the picture.

Earlier I complained that there was no natural isomorphism $V \cong V^\vee$.
But in fact, given an inner form
we can actually make such an identification:
that is we can naturally associate every linear map
$\xi \colon V \to k$ with a vector $v \in V$.

To see how we might do this, suppose $V = \RR^3$
for now with an orthonormal basis $e_1$, $e_2$, $e_3$.
How might we use the inner product to
represent a map from $V \to \RR$?
For example, take $\xi \in V^\vee$ by
$\xi(e_1) = 3$, $\xi(e_2) = 4$ and $\xi(e_3) = 5$.
Actually, I claim that
\[ \xi(v) = \left< v, 3e_1 + 4e_2 + 5e_3 \right> \]
for every $v$.
\begin{ques}
	Check this.
\end{ques}

And this works beautifully in the real case.
\begin{theorem}[$V \cong V^\vee$ for real inner forms]
	\label{thm:real_dual_isomorphic}
	Let $V$ be a finite-dimensional \emph{real}
	inner product space and $V^\vee$ its dual.
	Then the map $V \to V^\vee$ by
	\[ v \mapsto \left<  -, v \right> \in V^\vee \]
	is an isomorphism of real vector spaces.
\end{theorem}
\begin{proof}
	It suffices to show that the map is injective and surjective.
	\begin{itemize}
		\ii Injective: suppose $\left< v, v_1 \right> = \left< v, v_2 \right>$
		for every vector $v \in V$.
		This means $\left< v, v_1 - v_2 \right> = 0$ for every vector $v \in V$.
		This can only happen if $v_1 - v_2 = 0$; for example, take $v = v_1 - v_2$
		and use positive definiteness.
		\ii Surjective: take an orthonormal basis $e_1$, \dots $e_n$
		and let $e_1^\vee$, \dots, $e_n^\vee$ be the dual basis on $V^\vee$.
		Then $e_1$ maps to $e_1^\vee$, et cetera.
		\qedhere
	\end{itemize}
\end{proof}
Actually, since we already know $\dim V = \dim V^\vee$
we only had to prove one of the above.
As a matter of personal taste, I find the proof of injectivity more elegant,
and the proof of surjectivity more enlightening,
so I included both.
Thus
\begin{moral}
	If a real inner product space $V$ is given an inner form,
	then $V$ and $V^\vee$ are canonically isomorphic.
\end{moral}

Unfortunately, things go awry if $V$ is complex.
Here is the result:
\begin{theorem}[$V$ versus $V^\vee$ for complex inner forms]
	Let $V$ be a finite-dimensional \emph{complex}
	inner product space and $V^\vee$ its dual.
	Then the map $V \to V^\vee$ by
	\[ v \mapsto \left<  -, v \right> \in V^\vee \]
	is a bijection of sets.
\end{theorem}
Wait, what? Well, the proof above shows that it is both injective
and surjective, but why is it not an isomorphism?
The answer is that it is not a linear map:
since the form is sesquilinear we have for example
\[ iv \mapsto \left< -, iv\right> = -i \left< -, v\right> \]
which has introduced a minus sign!
In fact, it is an \emph{anti-linear} map, in the sense we defined before.

Eager readers might try to fix this by defining
the isomorphism $v \mapsto \left< v, - \right>$ instead.
However, this also fails, because the right-hand side
is not even an element of $V^\vee$:
it is an ``anti-linear'', not linear.

And so we are stuck.
Fortunately, we will only need the ``bijection'' result
for what follows, so we can continue on anyways.
(If you want to fix this, \Cref{prob:complex_conj_space}
gives a way to do so.)


\section{The adjoint (conjugate transpose)}
We will see that, as a result of the flipping above,
the \emph{conjugate transpose} is actually the better concept
for inner product spaces: since it can be defined using only the inner product
without making mention to dual spaces at all.
\begin{definition}
	Let $V$ and $W$ be finite-dimensional inner product spaces,
	and let $T \colon V \to W$.
	The \vocab{adjoint} (or \vocab{conjugate transpose})
	of $T$, denoted $T^\dagger \colon W \to V$,
	is defined as follows: for every vector $w \in W$,
	we let $T^\dagger(w) \in V$ be the unique vector with
	\[ \left< v, T^\dagger(w) \right>_V = \left< T(v), w \right>_W \]
	for every $v \in V$.
\end{definition}

Some immediate remarks about this definition:
\begin{itemize}
\ii Our $T^\dagger$ is well-defined,
because $v \mapsto \left< T(v), w \right>_W$ is some function in $V^\vee$,
and hence by the bijection earlier
it should be uniquely of the form $\left< -, v \right>$ for some $v \in V$.
\ii This map $T^\dagger$ is indeed a linear map (why?).
\ii The niceness of this definition is that it doesn't
make reference to any basis or even $V^\vee$,
so it is the ``right'' definition for a inner product space.
\end{itemize}

\begin{example}
	[Example of an adjoint map]
	We'll work over $\CC$, so the conjugates are more visible.
	Let's consider $V$ with orthonormal basis $e_1$, $e_2$, $e_3$
	and $W$ with orthonormal basis $f_1$, $f_2$.
	We put
	\begin{align*}
		T(e_1) &= if_1 + 2f_2 \\
		T(e_2) &= 3f_1 + 4f_2 \\
		T(e_3) &= 5f_1 + 6if_2.
	\end{align*}
	We compute $T^\dagger(f_1)$.
	It is the unique vector $x \in V$ such that
	\[ \left< v, x \right>_V = \left< T(v), f_1 \right>_W \]
	for any $v \in V$.
	If we expand $v = ae_1 + be_2 + ce_3$ the above equality becomes
	\begin{align*}
		\left< ae_1 + be_2 + ce_3, x \right>_V
		&= \left< T(ae_1 + be_2 + ce_3), f_1 \right>_W \\
		&= ia + 3b + 5c.
	\end{align*}
	However, since $x$ is in the second argument,
	this means we actually want to take
	\[ T^\dagger(f_1) = -ie_1 + 3e_2 + 5e_3 \]
	so that the sesquilinearity will conjugate the $i$.
\end{example}

The pattern continues, though we remind the reader that
we need the basis to be orthonormal to proceed.
\begin{theorem}
	[Adjoints are conjugate transposes]
	Fix an \emph{orthonormal} basis of a finite-dimensional inner product space $V$.
	Let $T \colon V \to V$ be a linear map.
	If we write $T$ as a matrix in this basis,
	then the matrix $T^\dagger$ (in the same basis)
	is the \emph{conjugate transpose} of the matrix of $T$;
	that is, the $(i,j)$th entry of $T^\vee$
	is the complex conjugate of the $(j,i)$th entry of $T$.
\end{theorem}
\begin{proof}
	One-line version: take $v$ and $w$ to be basis elements,
	and this falls right out.

	Full proof: let
	\[ T = \begin{bmatrix}
			a_{11} & \dots & a_{1n} \\
			\vdots & \ddots & \vdots \\
			a_{n1} & \dots & a_{nn}
		\end{bmatrix} \]
	in this basis $e_1$, \dots, $e_n$.
	Then, letting $w = e_i$ and $v = e_j$ we deduce that
	\[ \left< e_i, T^\dagger(e_j) \right> = \left< T(e_i) , e_j\right> = a_{ji}
		\implies
		\left< T^\dagger(e_j), e_i \right> = \ol{a_{ji}} \]
	for any $i$, which is enough to deduce the result.
\end{proof}

\section{Eigenvalues of normal maps}
We now come to the advertised theorem.
Restrict to the situation where $T \colon V \to V$.
You see, the world would be a very beautiful place if it turned out
that we could pick a basis of eigenvectors that was also \emph{orthonormal}.
This is of course far too much to hope for;
even without the orthonormal condition,
we saw that Jordan form could still have $1$'s off the diagonal.

However, it turns out that there is
a complete characterization of exactly when our overzealous dream is true.

\begin{definition}
	\label{def:hermitian}
	We say a linear map $T$
	(from a finite-dimensional inner product space to itself)
	is \vocab{normal} if $TT^\dagger = T^\dagger T$.

	We say a complex $T$ is \vocab{self-adjoint} or \vocab{Hermitian} if $T = T^\dagger$;
	i.e.\ as a matrix in any orthonormal basis, $T$ is its own conjugate transpose.
	For real $T$ we say ``self-adjoint'', ``Hermitian'' or \vocab{symmetric}.
\end{definition}
\begin{theorem}
	[Normal $\iff$ diagonalizable with orthonormal basis]
	Let $V$ be a finite-dimensional complex inner product space.
	A linear map $T \colon V \to V$ is normal
	if and only if one can pick an orthonormal basis of eigenvectors.
\end{theorem}
\begin{exercise}
	Show that if there exists such an orthonormal basis
	then $T \colon V \to V$ is normal,
	by writing $T$ as a diagonal matrix in that basis.
\end{exercise}
\begin{proof}
	This is long, and maybe should be omitted on a first reading.
	If $T$ has an orthonormal basis of eigenvectors,
	this result is immediate.

	Now assume $T$ is normal.
	We first prove $T$ is diagonalizable; this is the hard part.
	\begin{claim}
		If $T$ is normal, then $\ker T = \ker T^r = \ker T^\dagger$ for $r \ge 1$.
		(Here $T^r$ is $T$ applied $r$ times.)
	\end{claim}
	\begin{subproof}
		[Proof of Claim]
		Let $S = T^\dagger \circ T$, which is self-adjoint.
		We first note that $S$ is Hermitian and $\ker S = \ker T$.
		To see it's Hermitian, note
		$\left<Sv, w \right> = \left<Tv, Tw \right> = \left<v, S w \right>$.
		Taking $v = w$ also implies $\ker S \subseteq \ker T$
		(and hence equality since obviously $\ker T \subseteq \ker S$).

		First, since we have $\left< S^r(v), S^{r-2}(v) \right>
		= \left< S^{r-1}(v), S^{r-1}(v)\right>$,
		an induction shows that $\ker S = \ker S^r$ for $r \ge 1$.
		Now, since $T$ is normal, we have $S^r = (T^\dagger)^r \circ T^r$,
		and thus we have the inclusion
		\[ \ker T \subseteq \ker T^r \subseteq \ker S^r = \ker S = \ker T \]
		where the last equality follows from the first claim.
		Thus in fact $\ker T = \ker T^r$.

		Finally, to show equality with $\ker T^\dagger$ we
		\begin{align*}
			\left< Tv, Tv\right> &= \left< v, T^\dagger T v\right> \\
			&= \left< v, T T^\dagger v \right> \\
			&= \left< T^\dagger v, T^\dagger v \right>. \qedhere
		\end{align*}
	\end{subproof}

	Now consider the given $T$, and any $\lambda$.
	\begin{ques}
		Show that $(T - \lambda\id)^\dagger = T^\dagger - \ol\lambda \id$.
		Thus if $T$ is normal, so is $T - \lambda \id$.
	\end{ques}
	In particular, for any eigenvalue $\lambda$ of $T$,
	we find that $\ker (T-\lambda\id) = \ker(T-\lambda\id)^r$.
	This implies that all the Jordan blocks of $T$ have size $1$;
	i.e.\ that $T$ is in fact diagonalizable.
	Finally, we conclude that the eigenvectors of $T$ and $T^\dagger$ match,
	and the eigenvalues are complex conjugates.

	So, diagonalize $T$.
	We just need to show that if $v$ and $w$ are eigenvectors of $T$
	with distinct eigenvalues, then they are orthogonal.
	(We can use Gram-Schmidt on any eigenvalue that appears multiple times.)
	To do this, suppose $T(v) = \lambda v$ and $T(w) = \mu w$
	(thus $T^\dagger(w) = \ol\mu w $).
	Then
	\[ \lambda \left< v,w\right>
		= \left< \lambda v, w\right>
		= \left< Tv, w\right>
		= \left< v, T^\dagger(w)\right>
		= \left< v, \ol \mu w \right>
		= \mu \left< v, w\right>. \]
	Since $\lambda \neq \mu$, we conclude $\left< v,w \right> = 0$.
\end{proof}
This means that not only can we write
\[ T = \begin{bmatrix}
		\lambda_1 & \dots & \dots & 0 \\
		0 & \lambda_2 & \dots & 0 \\
		\vdots & \vdots & \ddots & \vdots \\
		0 & 0 & \dots & \lambda_n
	\end{bmatrix}
\]
but moreover that the basis associated with this matrix happens to be orthonormal vectors.

As a corollary:
\begin{theorem}[Hermitian matrices have real eigenvalues]
	A Hermitian matrix $T$ is diagonalizable,
	and all its eigenvalues are real.
\end{theorem}
\begin{proof}
	Obviously Hermitian $\implies$ normal,
	so write it in the orthonormal basis of eigenvectors.
	To see that the eigenvalues are real, note that $T = T^\dagger$
	means $\lambda_i = \ol{\lambda_i}$ for every $i$.
\end{proof}

\section{\problemhead}
\begin{sproblem}
	[Double dual]
	\onechili
	\label{prob:double_dual}
	Let $V$ be a finite-dimensional vector space.
	Prove that
	\begin{align*}
		V &\to (V^\vee)^\vee \\
		v &\mapsto \left( \xi \mapsto \xi(v) \right)
	\end{align*}
	gives an isomorphism.
	(This is significant because the isomorphism is \emph{canonical},
	and in particular does not depend on the choice of basis.
	So this is more impressive.)
	\begin{hint}
		You can \emph{prove} the result just by taking a basis
		$e_1$, \dots, $e_n$ of $V$
		and showing that it is a linear map sending $e_1$
		to the basis $(e_1^\vee)^\vee$.
	\end{hint}
\end{sproblem}

\begin{problem}
	[Fundamental theorem of linear algebra]
	\label{prob:fundamental_theorem_of_linalg}
	Let $T \colon V \to W$ be a map of finite-dimensional $k$-vector spaces.
	Prove that
	\[ \dim \img T = \dim \img T^\vee
		= \dim V - \dim \ker T = \dim W - \dim \ker T^\vee. \]
	\begin{hint}
		Use \Cref{thm:linear_map_basis} and it will be immediate
		(the four quantities equal the $k$ in the theorem).
	\end{hint}
	\begin{sol}
		By \Cref{thm:linear_map_basis},
		we may select $e_1$, \dots, $e_n$ a basis of $V$
		and $f_1$, \dots, $f_m$ a basis of $W$
		such that $T(e_i) = f_i$ for $i \le k$
		and $T(e_i) = 0$ for $i > k$.
		Then $T^\vee(f_i^\vee) = e_i^\vee$ for $i \le k$
		and $T^\vee(f_i^\vee) = 0$ for $i > k$.
		All four quantities are above are then equal to $k$.
	\end{sol}
\end{problem}

\begin{dproblem}
	[Row rank is column rank]
	\label{prob:row_rank_column_rank}
	A $m \times n$ matrix $M$ is given over some field $k$.
	The \emph{column rank} of $M$ is the dimension of the span in $k^{\oplus m}$
	of its $n$ column vectors.
	The \emph{row rank} of $M$ is the dimension of the span in $k^{\oplus n}$
	of its $m$ row vectors.
	Prove that the row rank and column rank are equal.
	\begin{hint}
		This actually is just the previous problem in disguise!
		The row rank is $\dim \img T^\vee$
		and the column rank is $\dim \img T$.
	\end{hint}
\end{dproblem}

\begin{problem}
	[The complex conjugate spaces]
	\label{prob:complex_conj_space}
	Let $V = (V, +, \cdot)$ be a complex vector space.
	Define the \vocab{complex conjugate vector space},
	denoted $\ol V = (V, +, \ast)$
	by changing just the multiplication:
	\[ c \ast v = \ol c \cdot v. \]
	Show that for any sesquilinear form on $V$,
	if $V$ is finite-dimensional, then
	\begin{align*}
		\ol V & \to V^\vee \\
		v &\mapsto \left< -, v \right>
	\end{align*}
	is an isomorphism of complex vector spaces.
\end{problem}

\begin{problem}
	[$T^\dagger$ vs $T^\vee$]
	Let $V$ and $W$ be real inner product spaces
	and let $T \colon V \to W$ be a linear map.
	Show that the following diagram commutes:
	\begin{center}
	\begin{tikzcd}
		W \ar[r, "T^\dagger"] \ar[d, "\cong"']
			& V \ar[d, "\cong"] \\
		W^\vee \ar[r, "T^\vee"']  & V^\vee
	\end{tikzcd}
	\end{center}
	Here the isomorphisms are $v \mapsto \left< -, v\right>$.
	Thus, for real inner product spaces,
	$T^\dagger$ is just $T^\vee$ with the duals eliminated
	(by \Cref{thm:real_dual_isomorphic}).
\end{problem}

\begin{problem}
	[Polynomial criteria for normality]
	Let $V$ be a finite-dimensional complex inner product space and let $T \colon V \to V$ be a linear map.
	Show that $T$ is normal if and only if there is a polynomial\footnote{Here,
			we mean $p(T)$ in the same composition sense as in Cayley-Hamilton.}
	$p \in \CC[t]$ such that \[ T^\dagger = p(T). \]
	\begin{hint}
		If there is a polynomial, check $TT^\dagger = T^\dagger T$ directly.
		If $T$ is normal, diagonalize it.
	\end{hint}
	\begin{sol}
		First, suppose $T^\ast = p(T)$.
		Then $T^\ast T = p(T) \cdot T = T \cdot p(T) = T T^\ast$ and we're done.

		Conversely, suppose $T$ is diagonalizable
		in a way compatible with the inner form
		(OK since $V$ is finite dimensional).
		Consider the orthonormal basis.
		Then $T$ consists of eigenvalues on the main diagonals
		and zeros elsewhere, say
		\[ T = \left(
			\begin{array}{cccc}
				\lambda_1 & 0 & \dots & 0 \\
				0 & \lambda_2 & \dots & 0 \\
				\vdots & \vdots & \ddots &  \vdots \\
				0 & 0 & \dots & \lambda_n
			\end{array}
			\right). \]
		In that case, we find that for any polynomial $q$ we have
		\[ q(T) = \left(
			\begin{array}{cccc}
				q(\lambda_1) & 0 & \dots & 0 \\
				0 & q(\lambda_2) & \dots & 0 \\
				\vdots & \vdots & \ddots &  \vdots \\
				0 & 0 & \dots & q(\lambda_n)
			\end{array}
			\right). \]
		and
		\[ T^\ast = \left(
			\begin{array}{cccc}
				\ol{\lambda_1} & 0 & \dots & 0 \\
				0 & \ol{\lambda_2} & \dots & 0 \\
				\vdots & \vdots & \ddots &  \vdots \\
				0 & 0 & \dots & \ol{\lambda_n}
			\end{array}
			\right). \]
		So we simply require a polynomial $q$
		such that $q(\lambda_i) = \ol{\lambda_i}$ for every $i$.
		Since there are finitely many $\lambda_i$,
		we can construct such a polynomial using Lagrange interpolation.
	\end{sol}
\end{problem}

\begin{problem}
	[Kronecker product of matrices]
	\onechili
	Find an equivalence between the following two definitions of the
	\href{https://en.wikipedia.org/wiki/Kronecker_product}{Kronecker product},
	the former from a mathematician and the latter from a computer scientist:
	\begin{itemize}
		\ii Suppose $A \colon V_1 \to W_1$ and $B \colon V_2 \to W_2$
		are linear maps of finite-dimensional vector spaces over $\RR$.
		Then we define $A \otimes B \colon V_1 \otimes V_2 \to W_1 \otimes W_2$
		on simple tensors by $v_1 \otimes v_2 \mapsto A(v_1) \otimes B(v_2)$.

		\ii Suppose $A$ is an $m \times n$ matrix and $B$ is a $p \times q$ matrix.
		Then $A \otimes B$ is an operator which takes a $q \times n$ matrix $X$
		and returns the $p \times m$ matrix $BXA^\top$.
	\end{itemize}
\end{problem}

\begin{dproblem}
	\label{prob:rank_Mdagger_M}
	Let $M$ be an $m \times n$ matrix of complex numbers.
	Show that $M^\dagger M$ and $M$ have equal rank.
	(Try to find a basis-free proof.)
	\begin{hint}
		I do not recommend picking any basis.
		Instead, show directly that $\ker(T^\dagger T) = \ker(T)$ for any map $T$.
		(This is better than having the same dimension: the kernels actually match.)
	\end{hint}
\end{dproblem}
